class Solution(object):
    def maxProfit(self, prices):
        """
        :type prices: List[int]
        :rtype: int
        """
        n = len(prices)
        if n < 2:
            return 0
            
        # 使用动态规划，分别计算第一次和第二次交易的最大利润
        # 第一次交易的最大利润
        first_profit = [0] * n
        min_price = prices[0]
        for i in range(1, n):
            min_price = min(min_price, prices[i])
            first_profit[i] = max(first_profit[i-1], prices[i] - min_price)
            
        # 第二次交易的最大利润
        second_profit = [0] * n
        max_price = prices[-1]
        for i in range(n-2, -1, -1):
            max_price = max(max_price, prices[i])
            second_profit[i] = max(second_profit[i+1], max_price - prices[i])
            
        # 计算两次交易的最大总利润
        max_total_profit = 0
        for i in range(n):
            max_total_profit = max(max_total_profit, first_profit[i] + second_profit[i])
            
        return max_total_profit


if __name__ == "__main__":
    so = Solution()
    prices = [1, 2, 3, 4, 5]
    print(so.maxProfit(prices))
